package 剑指Offer._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/7/2 21:02
 * 二维数组中的查找
 * 算法：数组
 * 从右上角开始查找
 * target > matrix[i][j], 向下
 * target < matrix[i][j], 向左
 * 也可以从左下角开始
 * 时间复杂度: O(m + n)
 */
public class _04 {

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int m = matrix.length, n;
        if (m == 0) return false;
        n = matrix[0].length;
        if (n == 0) return false;
        int r = 0, c = n - 1;
        while (r < m && c >= 0) {
            if (target == matrix[r][c]) return true;
            else if (target > matrix[r][c]) ++r;
            else --c;
        }
        return false;
    }

}
